/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* newhead=NULL,*n1=NULL;
    if(list1==NULL)return list2;
    if(list2==NULL)return list1;
    struct ListNode *l1=list1,*l2=list2,*tmp=NULL;

    while(l1&&l2)
    {
        if(l1->val<=l2->val)
        {
            if(!newhead)
            {
                newhead=n1=l1;
            }
            else
            {
                n1->next=l1;
                n1=n1->next;
            }
            l1=l1->next;
        }
        else{
            if(!newhead)
            {
                newhead=n1=l2;
            }
            else
            {
                n1->next=l2;
                n1=n1->next;
            }
            l2=l2->next;
        }
    }
    if(l1)n1->next=l1;
    if(l2)n1->next=l2;
    return newhead;
}